{
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "## 8.22 \u4e0d\u7528\u9012\u5f52\u5b9e\u73b0\u8bbf\u95ee\u8005\u6a21\u5f0f\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "### \u95ee\u9898\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "\u4f60\u4f7f\u7528\u8bbf\u95ee\u8005\u6a21\u5f0f\u904d\u5386\u4e00\u4e2a\u5f88\u6df1\u7684\u5d4c\u5957\u6811\u5f62\u6570\u636e\u7ed3\u6784\uff0c\u5e76\u4e14\u56e0\u4e3a\u8d85\u8fc7\u5d4c\u5957\u5c42\u7ea7\u9650\u5236\u800c\u5931\u8d25\u3002\n\u4f60\u60f3\u6d88\u9664\u9012\u5f52\uff0c\u5e76\u540c\u65f6\u4fdd\u6301\u8bbf\u95ee\u8005\u7f16\u7a0b\u6a21\u5f0f\u3002"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "### \u89e3\u51b3\u65b9\u6848\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "\u901a\u8fc7\u5de7\u5999\u7684\u4f7f\u7528\u751f\u6210\u5668\u53ef\u4ee5\u5728\u6811\u904d\u5386\u6216\u641c\u7d22\u7b97\u6cd5\u4e2d\u6d88\u9664\u9012\u5f52\u3002\n\u57288.21\u5c0f\u8282\u4e2d\uff0c\u6211\u4eec\u7ed9\u51fa\u4e86\u4e00\u4e2a\u8bbf\u95ee\u8005\u7c7b\u3002\n\u4e0b\u9762\u6211\u4eec\u5229\u7528\u4e00\u4e2a\u6808\u548c\u751f\u6210\u5668\u91cd\u65b0\u5b9e\u73b0\u8fd9\u4e2a\u7c7b\uff1a"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {},
      "outputs": [],
      "source": [
        "import types\n\nclass Node:\n    pass\n\nclass NodeVisitor:\n    def visit(self, node):\n        stack = [node]\n        last_result = None\n        while stack:\n            try:\n                last = stack[-1]\n                if isinstance(last, types.GeneratorType):\n                    stack.append(last.send(last_result))\n                    last_result = None\n                elif isinstance(last, Node):\n                    stack.append(self._visit(stack.pop()))\n                else:\n                    last_result = stack.pop()\n            except StopIteration:\n                stack.pop()\n\n        return last_result\n\n    def _visit(self, node):\n        methname = 'visit_' + type(node).__name__\n        meth = getattr(self, methname, None)\n        if meth is None:\n            meth = self.generic_visit\n        return meth(node)\n\n    def generic_visit(self, node):\n        raise RuntimeError('No {} method'.format('visit_' + type(node).__name__))"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "\u5982\u679c\u4f60\u4f7f\u7528\u8fd9\u4e2a\u7c7b\uff0c\u4e5f\u80fd\u8fbe\u5230\u76f8\u540c\u7684\u6548\u679c\u3002\u4e8b\u5b9e\u4e0a\u4f60\u5b8c\u5168\u53ef\u4ee5\u5c06\u5b83\u4f5c\u4e3a\u4e0a\u4e00\u8282\u4e2d\u7684\u8bbf\u95ee\u8005\u6a21\u5f0f\u7684\u66ff\u4ee3\u5b9e\u73b0\u3002\n\u8003\u8651\u5982\u4e0b\u4ee3\u7801\uff0c\u904d\u5386\u4e00\u4e2a\u8868\u8fbe\u5f0f\u7684\u6811\uff1a"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {},
      "outputs": [],
      "source": [
        "class UnaryOperator(Node):\n    def __init__(self, operand):\n        self.operand = operand\n\nclass BinaryOperator(Node):\n    def __init__(self, left, right):\n        self.left = left\n        self.right = right\n\nclass Add(BinaryOperator):\n    pass\n\nclass Sub(BinaryOperator):\n    pass\n\nclass Mul(BinaryOperator):\n    pass\n\nclass Div(BinaryOperator):\n    pass\n\nclass Negate(UnaryOperator):\n    pass\n\nclass Number(Node):\n    def __init__(self, value):\n        self.value = value\n\n# A sample visitor class that evaluates expressions\nclass Evaluator(NodeVisitor):\n    def visit_Number(self, node):\n        return node.value\n\n    def visit_Add(self, node):\n        return self.visit(node.left) + self.visit(node.right)\n\n    def visit_Sub(self, node):\n        return self.visit(node.left) - self.visit(node.right)\n\n    def visit_Mul(self, node):\n        return self.visit(node.left) * self.visit(node.right)\n\n    def visit_Div(self, node):\n        return self.visit(node.left) / self.visit(node.right)\n\n    def visit_Negate(self, node):\n        return -self.visit(node.operand)\n\nif __name__ == '__main__':\n    # 1 + 2*(3-4) / 5\n    t1 = Sub(Number(3), Number(4))\n    t2 = Mul(Number(2), t1)\n    t3 = Div(t2, Number(5))\n    t4 = Add(Number(1), t3)\n    # Evaluate it\n    e = Evaluator()\n    print(e.visit(t4))  # Outputs 0.6"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "\u5982\u679c\u5d4c\u5957\u5c42\u6b21\u592a\u6df1\u90a3\u4e48\u4e0a\u8ff0\u7684Evaluator\u5c31\u4f1a\u5931\u6548\uff1a"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {},
      "outputs": [],
      "source": [
        "a = Number(0)\nfor n in range(1, 100000):\na = Add(a, Number(n))\ne = Evaluator()\ne.visit(a)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "\u73b0\u5728\u6211\u4eec\u7a0d\u5fae\u4fee\u6539\u4e0b\u4e0a\u9762\u7684Evaluator\uff1a"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {},
      "outputs": [],
      "source": [
        "class Evaluator(NodeVisitor):\n    def visit_Number(self, node):\n        return node.value\n\n    def visit_Add(self, node):\n        yield (yield node.left) + (yield node.right)\n\n    def visit_Sub(self, node):\n        yield (yield node.left) - (yield node.right)\n\n    def visit_Mul(self, node):\n        yield (yield node.left) * (yield node.right)\n\n    def visit_Div(self, node):\n        yield (yield node.left) / (yield node.right)\n\n    def visit_Negate(self, node):\n        yield - (yield node.operand)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "\u518d\u6b21\u8fd0\u884c\uff0c\u5c31\u4e0d\u4f1a\u62a5\u9519\u4e86\uff1a"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {},
      "outputs": [],
      "source": [
        "a = Number(0)\nfor n in range(1,100000):\n    a = Add(a, Number(n))\ne = Evaluator()\ne.visit(a)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "\u5982\u679c\u4f60\u8fd8\u60f3\u6dfb\u52a0\u5176\u4ed6\u81ea\u5b9a\u4e49\u903b\u8f91\u4e5f\u6ca1\u95ee\u9898\uff1a"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {},
      "outputs": [],
      "source": [
        "class Evaluator(NodeVisitor):\n    ...\n    def visit_Add(self, node):\n        print('Add:', node)\n        lhs = yield node.left\n        print('left=', lhs)\n        rhs = yield node.right\n        print('right=', rhs)\n        yield lhs + rhs\n    ..."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "\u4e0b\u9762\u662f\u7b80\u5355\u7684\u6d4b\u8bd5\uff1a"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {},
      "outputs": [],
      "source": [
        "e = Evaluator()\ne.visit(t4)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "### \u8ba8\u8bba\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "\u8fd9\u4e00\u5c0f\u8282\u6211\u4eec\u6f14\u793a\u4e86\u751f\u6210\u5668\u548c\u534f\u7a0b\u5728\u7a0b\u5e8f\u63a7\u5236\u6d41\u65b9\u9762\u7684\u5f3a\u5927\u529f\u80fd\u3002\n\u907f\u514d\u9012\u5f52\u7684\u4e00\u4e2a\u901a\u5e38\u65b9\u6cd5\u662f\u4f7f\u7528\u4e00\u4e2a\u6808\u6216\u961f\u5217\u7684\u6570\u636e\u7ed3\u6784\u3002\n\u4f8b\u5982\uff0c\u6df1\u5ea6\u4f18\u5148\u7684\u904d\u5386\u7b97\u6cd5\uff0c\u7b2c\u4e00\u6b21\u78b0\u5230\u4e00\u4e2a\u8282\u70b9\u65f6\u5c06\u5176\u538b\u5165\u6808\u4e2d\uff0c\u5904\u7406\u5b8c\u540e\u5f39\u51fa\u6808\u3002visit() \u65b9\u6cd5\u7684\u6838\u5fc3\u601d\u8def\u5c31\u662f\u8fd9\u6837\u3002"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "\u53e6\u5916\u4e00\u4e2a\u9700\u8981\u7406\u89e3\u7684\u5c31\u662f\u751f\u6210\u5668\u4e2dyield\u8bed\u53e5\u3002\u5f53\u78b0\u5230yield\u8bed\u53e5\u65f6\uff0c\u751f\u6210\u5668\u4f1a\u8fd4\u56de\u4e00\u4e2a\u6570\u636e\u5e76\u6682\u65f6\u6302\u8d77\u3002\n\u4e0a\u9762\u7684\u4f8b\u5b50\u4f7f\u7528\u8fd9\u4e2a\u6280\u672f\u6765\u4ee3\u66ff\u4e86\u9012\u5f52\u3002\u4f8b\u5982\uff0c\u4e4b\u524d\u6211\u4eec\u662f\u8fd9\u6837\u5199\u9012\u5f52\uff1a"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {},
      "outputs": [],
      "source": [
        "value = self.visit(node.left)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "\u73b0\u5728\u6362\u6210yield\u8bed\u53e5\uff1a"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {},
      "outputs": [],
      "source": [
        "value = yield node.left"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "\u5b83\u4f1a\u5c06 node.left \u8fd4\u56de\u7ed9 visit() \u65b9\u6cd5\uff0c\u7136\u540e visit() \u65b9\u6cd5\u8c03\u7528\u90a3\u4e2a\u8282\u70b9\u76f8\u5e94\u7684 visit_Name() \u65b9\u6cd5\u3002\nyield\u6682\u65f6\u5c06\u7a0b\u5e8f\u63a7\u5236\u5668\u8ba9\u51fa\u7ed9\u8c03\u7528\u8005\uff0c\u5f53\u6267\u884c\u5b8c\u540e\uff0c\u7ed3\u679c\u4f1a\u8d4b\u503c\u7ed9value\uff0c"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "\u770b\u5b8c\u8fd9\u4e00\u5c0f\u8282\uff0c\u4f60\u4e5f\u8bb8\u60f3\u53bb\u5bfb\u627e\u5176\u5b83\u6ca1\u6709yield\u8bed\u53e5\u7684\u65b9\u6848\u3002\u4f46\u662f\u8fd9\u4e48\u505a\u6ca1\u6709\u5fc5\u8981\uff0c\u4f60\u5fc5\u987b\u5904\u7406\u5f88\u591a\u68d8\u624b\u7684\u95ee\u9898\u3002\n\u4f8b\u5982\uff0c\u4e3a\u4e86\u6d88\u9664\u9012\u5f52\uff0c\u4f60\u5fc5\u987b\u8981\u7ef4\u62a4\u4e00\u4e2a\u6808\u7ed3\u6784\uff0c\u5982\u679c\u4e0d\u4f7f\u7528\u751f\u6210\u5668\uff0c\u4ee3\u7801\u4f1a\u53d8\u5f97\u5f88\u81c3\u80bf\uff0c\u5230\u5904\u90fd\u662f\u6808\u64cd\u4f5c\u8bed\u53e5\u3001\u56de\u8c03\u51fd\u6570\u7b49\u3002\n\u5b9e\u9645\u4e0a\uff0c\u4f7f\u7528yield\u8bed\u53e5\u53ef\u4ee5\u8ba9\u4f60\u5199\u51fa\u975e\u5e38\u6f02\u4eae\u7684\u4ee3\u7801\uff0c\u5b83\u6d88\u9664\u4e86\u9012\u5f52\u4f46\u662f\u770b\u4e0a\u53bb\u53c8\u5f88\u50cf\u9012\u5f52\u5b9e\u73b0\uff0c\u4ee3\u7801\u5f88\u7b80\u6d01\u3002"
      ]
    }
  ],
  "metadata": {
    "kernelspec": {
      "display_name": "Python 3",
      "language": "python",
      "name": "python3"
    },
    "language_info": {
      "codemirror_mode": {
        "name": "ipython",
        "version": 3
      },
      "file_extension": ".py",
      "mimetype": "text/x-python",
      "name": "python",
      "nbconvert_exporter": "python",
      "pygments_lexer": "ipython3",
      "version": "3.7.1"
    },
    "toc": {
      "base_numbering": 1,
      "nav_menu": {},
      "number_sections": true,
      "sideBar": true,
      "skip_h1_title": true,
      "title_cell": "Table of Contents",
      "title_sidebar": "Contents",
      "toc_cell": false,
      "toc_position": {},
      "toc_section_display": true,
      "toc_window_display": true
    }
  },
  "nbformat": 4,
  "nbformat_minor": 2
}